แรกเริ่มเกิดจากนโยบายทางด้านกีฬาของประเทศไทย ที่ต้องการให้ประชาชนมีส่วนร่วมในด้านการกีฬา และพัฒนาวงการฟุตบอลอาชีพของไทย ซึ่งจังหวัดมุกดาหารได้เริ่มก่อตั้งทีมสโมสรฟุตบอลเป็นของตัวเอง ลงทะเบียนกับสมาคมฟุตบอลแห่งประเทศไทย ในพระบรมราชูปถัมภ์ ในชื่อเริ่มแรกว่า สโมสรฟุตบอลจังหวัดมุกดาหาร ต่อมาได้มีการร่วมมือด้านกีฬากับแขวงสุวรรณเขต ประเทศลาว จึงได้เปลี่ยนชื่อเป็น สโมสรฟุตบอลมุกดาหาร-สะหวันนะเขต (Mukdahan-Savannakhet Football Club) โดยมีฉายาในขณะนั้นว่า แก้วมุกดา (The Perfume Flower Trees) ซึ่งเป็นต้นไม้ชนิดหนึ่ง และชื่อมีความคล้องจองกับสถานที่ท่องเที่ยวที่เป็นสัญลักษณ์ยุคใหม่ของจังหวัดคือ หอแก้วมุกดาหารหรือหอแก้วมุกดาหารเฉลิมพระเกียรติกาญจนาภิเษก คือ หอสังเกตการณ์ที่มีความสูง 65.50 เมตร สร้างขึ้นใน พ.ศ. 2539 ในพระราชพิธีฉลองสิริราชสมบัติในพระบาทสมเด็จพระเจ้าอยู่หัวภูมิพลอดุลยเดชมหาราช รัชกาลที่ 9 ครบ 50 ปี) ทีมสโมสรฟุตบอลมุกดาหาร-สะหวันนะเขตมีการเปลี่ยนโลโก้สัญลักษณ์ จากสัญลักษณ์หลักที่เป็นรูปหอแก้วมุกดาหาร เป็นรูปสัญลักษณ์ของ พญานาค ซึ่งเป็นตำนานตามความเชื่อท้องถิ่นของจังหวัด

ต่อมาเมื่อปี พ.ศ. 2553 สโมสรฟุตบอลมุกดาหาร-สะหวันนะเขต ได้มีการเปลี่ยนแปลงโครงสร้างการบริหารและมีการเปลี่ยนแปลงชื่อสโมสรเป็น สโมสรฟุตบอลมุกดาหาร ซิตี้ ครั้งนี้มีการร่วมมือกัน ระหว่างภาคส่วนมากขึ้น โดยภาคส่วนราชการและกลุ่มนักธุรกิจผู้รักกีฬาฟุตบอลชาวมุกดาหาร และได้รับอนุมัติแผนงานดำเนินงาน ซึ่งรับรองโดยท่านผู้ว่าราชการจังหวัดมุกดาหารในขณะนั้น คือ นายชาญวิทย์ วสยางกูร โดยนโยบายหลักของทีม คือ ต้องการให้ประชาชนชาวมุกดาหาร และเยาวชนในจังหวัดมุกดาหาร หันมาสนใจการแข่งขันกีฬาฟุตบอล ใช้เวลาว่างทำกิจกรรมกับครอบครัวในวันสุดสัปดาห์ และห่างไกลยาเสพติด นอกจากนั้นแล้ว ยังมีส่วนช่วยในการเสริมความสัมพันธ์ในด้านการกีฬา ระหว่าง เมืองคู่แฝดของจังหวัดมุกดาหาร คือ แขวงสุวรรณเขต ประเทศลาว ในขณะนั้นทีมมุกดาหาร ซิตี้ ได้มีโควต้านักกีฬาที่เป็น ชาวสุวรรณเขต รวมอยู่ในโควตานักกีฬาต่างชาติอีกด้วย รวมไปถึงแผนการใช้สนามเมืองสุวรรณเขตเป็นสนามเหย้าในบางนัด เพื่อสร้างความสัมพันธ์อันดีระหว่างกันกับกับทีมงานของมุกดาหาร ซิตี้ ภาคจังหวัดและแขวงสุวรรณเขต (เมืองไกสอน พมวิหาน)

ในขณะนั้นทีมมุกดาหารซิตี้ บริหารงานโดยประธานสโมสร พล.ต.ต. พิสัณห์ อาวีกร วรเทพนิตินันท์ ส่วนทีมนักกีฬาและสตาฟโค้ชบรการงานโดย ผู้จัดการทีม นายราชัน โภคสวัสดิ์ และหัวหน้าทีมผู้ฝึกสอน อ.วิลาศ ทิพรส มีความเชื่อว่าการบริหารงานอย่างมืออาชีพ และการทำทีมจากผู้มีประสบการณ์ จะสามารถนำทีมมุกดาหารซิตี้ ขึ้นสู่ Top 10 ของลีกภูมิภาคได้ ซึ่งต่อมาเมื่อผ่านไป 5 ฤดูกาล เป้าหมายดังกล่าวก็ยังไม่ประสบความสำเร็จเท่าที่ควร

สโมสรฟุตบอลมุกดาหาร ซิตี้ ได้มีการปรับเปลี่ยนโครงสร้างครั้งใหม่และเปลี่ยนชื่อสโมสรอีกครั้งเป็น สโมสรฟุตบอลมุกดาหาร ลำโขง มีประธานสโมสรท่านปัจจุบันคือ พล.ท.จิรศักดิ์ บุตรเนียร ผู้จัดการทีมคือ นายสุธี บัวสด (สมาชิกสภาจังหวัด) ผู้ฝึกสอนหลัก คือ นายศรีนคร บุตรโคตร

เมื่อวันที่ 20 พฤศจิกายน 2559 ได้ทำการคัดเลือกนักเตะเข้าสู่ทีม หลังจากหยุดพักการแข่งขันเมื่อจบฤดูกาล 2016 ซึ่งมีนักเตะจากต่างชาติทั้ง ญี่ปุน เกาหลี รวมถึงนักเตะผิวสี นักเตะมุกดาหาร ลำโขง บางส่วน และนักเตะจังหวัดใกล้เคียง ต่างเข้าร่วมในการคัดตัว ในครั้งนี้เกือบ 100 คน โดยได้กลุ่มนายทุนภาคตะวันออก มาเทคโอเวอร์ทำทีมแทนในนาม มุกดาหาร ไชยยืนยง หรือบึกพิฆาต